/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.MergeableAddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.VisibleForTesting
import java.io.Serializable
import java.lang.IllegalArgumentException
import java.util.*
import kotlin.Comparator
import kotlin.math.ceil
import kotlin.math.ln

/**
 * A binary tree soft addressable heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * If n elements are inserted into a soft heap, then up to &#949;n of the
 * elements still contained in the heap, for a given error parameter &#949;, may
 * be corrupted, i.e., have their keys artificially increased. In exchange for
 * allowing these corruptions, each soft heap operation is performed in O(log
 * 1/&#949;) amortized time. Note that n here is the number of elements inserted
 * into the heaps, not the current number of elements in the heap which may be
 * considerably smaller. Moreover the user has no control on which elements may
 * be corrupted.
 *
 *
 *
 * This variant of the soft heap is due to Kaplan and Zwick, described in detail
 * in the following
 * [paper](http://dx.doi.org/10.1137/1.9781611973068.53):
 *
 *  * Haim Kaplan and Uri Zwick, A simpler implementation and analysis of
 * Chazelle's Soft Heaps, In Proceedings of the 20th Annual ACM-SIAM Symposium
 * on Discrete Algorithms (SODA 2009), 477--485, 2009.
 *
 *
 *
 *
 * Note that the operation `decreaseKey()` always throws an
 * [UnsupportedOperationException] as a soft heap does not support such an
 * operation.
 *
 *
 *
 * All the above bounds, however, assume that the user does not perform
 * cascading melds on heaps such as:
 *
 * <pre>
 * d.meld(e);
 * c.meld(d);
 * b.meld(c);
 * a.meld(b);
</pre> *
 *
 * The above scenario, although efficiently supported by using union-find with
 * path compression, invalidates the claimed bounds.
 *
 *
 *
 * Note that the ordering maintained by a soft heap, like any heap, and whether
 * or not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the `Heap`
 * interface. (See `Comparable` or `Comparator` for a precise
 * definition of *consistent with equals*.) This is so because the
 * `Heap` interface is defined in terms of the `equals` operation,
 * but a pairing heap performs all key comparisons using its `compareTo`
 * (or `compare`) method, so two keys that are deemed equal by this method
 * are, from the standpoint of the heap, equal. The behavior of a heap
 * *is* well-defined even if its ordering is inconsistent with
 * `equals`; it just fails to obey the general contract of the
 * `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
class BinaryTreeSoftAddressableHeap<K, V> @JvmOverloads constructor(
    errorRate: Double,
    comparator: Comparator<in K?>? = null
) : MergeableAddressableHeap<K, V>, Serializable {
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    private val comparator: Comparator<in K?>?

    /**
     * Tree nodes with less or equal than this rank will have no corrupted keys.
     */
    private val rankLimit: Int

    /**
     * The root list, in non-decreasing rank order.
     */
    @JvmField
    @VisibleForTesting
    val rootList: RootList

    /**
     * Size of the heap.
     */
    private var size: Long

    /**
     * Used to reference the current heap or some other heap in case of melding,
     * so that handles remain valid even after a meld, without having to iterate
     * over them.
     *
     * In order to avoid maintaining a full-fledged union-find data structure,
     * we disallow a heap to be used in melding more than once. We use however,
     * path-compression in case of cascading melds, that it, a handle moves from
     * one heap to another and then another.
     */
    private var other: BinaryTreeSoftAddressableHeap<K, V>

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param errorRate
     * the error rate
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @throws IllegalArgumentException
     * if the error rate is less or equal to zero
     * @throws IllegalArgumentException
     * if the error rate is greater or equal to one
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys. All
     * keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     * @param errorRate
     * the error rate
     * @throws IllegalArgumentException
     * if the error rate is less or equal to zero
     * @throws IllegalArgumentException
     * if the error rate is greater or equal to one
     */
    init {
        if (java.lang.Double.compare(errorRate, 0.0) <= 0) {
            throw IllegalArgumentException("Error rate must be positive")
        }
        if (java.lang.Double.compare(errorRate, 1.0) >= 0) {
            throw IllegalArgumentException("Error rate must be less than one")
        }
        this.rankLimit = ceil(ln(1.0 / errorRate) / ln(2.0)).toInt() + 5
        this.rootList = RootList()
        this.comparator = comparator
        this.size = 0
        this.other = this
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        /**
         * {@inheritDoc}
         */
        get() {
            return size == 0L
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime(amortized = false)
    override fun clear() {
        rootList.head = null
        rootList.tail = null
        size = 0
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalArgumentException
     * if `other` has a different error rate
     */
    override fun meld(other: MergeableAddressableHeap<K, V>) {
        val h: BinaryTreeSoftAddressableHeap<K, V> = other as BinaryTreeSoftAddressableHeap<K, V>

        // check same comparator
        if (comparator != null) {
            if (h.comparator == null || !(h.comparator == comparator)) {
                throw IllegalArgumentException("Cannot meld heaps using different comparators!")
            }
        } else if (h.comparator != null) {
            throw IllegalArgumentException("Cannot meld heaps using different comparators!")
        }

        if (rankLimit != h.rankLimit) {
            throw IllegalArgumentException("Cannot meld heaps with different error rates!")
        }

        if (h.other !== h) {
            throw IllegalStateException("A heap cannot be used after a meld.")
        }

        // perform the meld
        mergeInto(h.rootList.head, h.rootList.tail)
        size += h.size

        // clear other
        h.size = 0
        h.rootList.head = null
        h.rootList.tail = null

        // take ownership
        h.other = this
    }

    /**
     * {@inheritDoc}
     */
    override fun insert(key: K, value: V?): SoftHandle {
        if (other !== this) {
            throw IllegalStateException("A heap cannot be used after a meld")
        }
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }
        /*
         * Create a single element heap
         */
        val n = SoftHandle(this, key, value)
        val treeNode: TreeNode = TreeNode(n)
        val rootListNode: RootListNode = RootListNode(treeNode)

        /*
         * Merge new list into old list
         */
        mergeInto(rootListNode, rootListNode)

        size++
        return n
    }

    /**
     * {@inheritDoc}
     */
    override fun insert(key: K): SoftHandle {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    override fun findMin(): SoftHandle {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return rootList.head!!.suffixMin.root.cHead!!
    }

    /**
     * {@inheritDoc}
     */
    override fun deleteMin(): SoftHandle {
        if (size == 0L) {
            throw NoSuchElementException()
        }

        // find tree with minimum
        val minRootListNode: RootListNode = rootList.head!!.suffixMin
        val root: TreeNode = minRootListNode.root

        // remove from list
        val result: SoftHandle? = root.cHead
        if (result!!.next != null) {
            result.next!!.prev = null
            result.next!!.tree = root
        }
        root.cHead = result.next
        root.cSize--

        // replenish keys if needed
        if (root.cHead == null || root.cSize <= targetSize(root.rank) / 2) {
            if (root.left != null || root.right != null) {
                // get keys from children
                sift(root)
                updateSuffixMin(minRootListNode)
            } else if (root.cHead == null) {
                // no children and empty list, just remove the tree
                val minRootPrevListNode: RootListNode? = minRootListNode.prev
                deleteNode(minRootListNode)
                updateSuffixMin(minRootPrevListNode)
            }
        }

        result.next = null
        result.prev = null
        result.tree = null
        size--
        return result
    }

    // --------------------------------------------------------------------
    @VisibleForTesting
    inner class RootList() : Serializable {
        @JvmField
        var head: RootListNode? = null
        @JvmField
        var tail: RootListNode? = null
        
    }

    // --------------------------------------------------------------------
    @VisibleForTesting
    inner class RootListNode(@JvmField var root: TreeNode) : Serializable {
        @JvmField
        var next: RootListNode?
        @JvmField
        var prev: RootListNode?
        @JvmField
        var suffixMin: RootListNode

        init {
            root.parent = this
            this.suffixMin = this
            this.next = null
            this.prev = null
        }
    }

    // --------------------------------------------------------------------
    @VisibleForTesting
    inner class TreeNode @JvmOverloads constructor(// corrupted list head
        @JvmField var cHead: SoftHandle? = null
    ) : Serializable {
        // rank
        @JvmField
        var rank: Int = 0

        // parent
        @JvmField
        var parent: Any? = null

        // left child
        @JvmField
        var left: TreeNode? = null

        // right child
        @JvmField
        var right: TreeNode? = null

        // corrupted list tail
        var cTail: SoftHandle? = cHead

        /*
         * Corrupted list size. This may be larger than the actual size as it
         * contains also a count of ghost elements (deleted by using directly
         * the handle). Checking whether the corrupted list is empty should be
         * performed using cHead.
         */
        @JvmField
        var cSize: Long = 0

        // corrupted key
        @JvmField
        var cKey: K? = null

        init {
            if (cHead != null) {
                this.cSize = 1
                this.cKey = cHead!!.key
                cHead!!.tree = this
            } else {
                this.cSize = 0
                this.cKey = null
            }
        }
    }

    // --------------------------------------------------------------------
    @VisibleForTesting
    inner class SoftHandle(/*
         * We maintain explicitly the belonging heap, instead of using an inner
         * class due to possible cascading melding.
         */var heap: BinaryTreeSoftAddressableHeap<K, V>,
                           /**
                            * {@inheritDoc}
                            */
                           override var key: K,
                           /**
                            * {@inheritDoc}
                            */
                           override var value: V?
    ) : AddressableHeap.Handle<K, V>, Serializable {
        /**
         * {@inheritDoc}
         */
        @JvmField
        var next: SoftHandle? = null
        var prev: SoftHandle? = null

        /*
         * We maintain the invariant that the first node of a list must contain
         * the tree that it belongs. Due to appending lists, other nodes may
         * point to the wrong tree.
         */
        @JvmField
        var tree: TreeNode? = null

        /**
         * {@inheritDoc}
         *
         * @throws UnsupportedOperationException
         * always, as this operation is not supported in soft heaps
         */
        override fun decreaseKey(newKey: K) {
            throw UnsupportedOperationException("Not supported in a soft heap")
        }

        /**
         * {@inheritDoc}
         */
        override fun delete() {
            owner.delete(this)
        }

        /*
        * Get the owner heap of the handle. This is union-find with
        * path-compression between heaps.
        */
        val owner: BinaryTreeSoftAddressableHeap<K, V>
            get() {
                if (heap.other !== heap) {
                    // find root
                    var root: BinaryTreeSoftAddressableHeap<K, V> = heap
                    while (root !== root.other) {
                        root = root.other
                    }
                    // path-compression
                    var cur: BinaryTreeSoftAddressableHeap<K, V> = heap
                    while (cur.other !== root) {
                        val nextOne: BinaryTreeSoftAddressableHeap<K, V> = cur.other
                        cur.other = root
                        cur = nextOne
                    }
                    heap = root
                }
                return heap
            }
    }

    /**
     * Compute the target size for a particular rank.
     *
     * @param rank
     * the rank
     * @return the target size
     */
    private fun targetSize(rank: Int): Long {
        return if (rank <= rankLimit) 1 else TARGET_SIZE.get(rank - rankLimit)
    }

    /**
     * Sift elements from children nodes until the current node has enough
     * elements in its list.
     *
     * @param x
     * the node
     */
    private fun sift(x: TreeNode?) {
        var x: TreeNode? = x
        val stack: Deque<TreeNode?> = ArrayDeque()
        stack.push(x)

        while (!stack.isEmpty()) {
            x = stack.peek()
            var xLeft: TreeNode? = x!!.left
            val xRight: TreeNode? = x.right

            // if leaf or list has enough elements, skip
            if (xLeft == null && xRight == null || x.cHead != null && x.cSize >= targetSize(x.rank)) {
                stack.pop()
                continue
            }

            // swap if needed
            if (xLeft == null || xRight != null
                && (((comparator == null && (xLeft.cKey as Comparable<K?>?)!!.compareTo(xRight.cKey) > 0)
                        || (comparator != null && comparator.compare(xLeft.cKey, xRight.cKey) > 0)))
            ) {
                x.left = xRight
                x.right = xLeft
                xLeft = x.left
            }

            // grab non-empty list from left child
            xLeft!!.cTail!!.next = x.cHead
            if (x.cHead != null) {
                x.cHead!!.prev = xLeft.cTail
            }
            x.cHead = xLeft.cHead
            if (x.cTail == null) {
                x.cTail = xLeft.cTail
            }
            x.cHead!!.tree = x
            x.cSize += xLeft.cSize

            // set new corrupted key
            x.cKey = xLeft.cKey

            // clear left child list
            xLeft.cKey = null
            xLeft.cHead = null
            xLeft.cTail = null
            xLeft.cSize = 0

            // recursively to left child if not a leaf
            if (xLeft.left != null || xLeft.right != null) {
                stack.push(xLeft)
            } else {
                x.left = null
            }
        }
    }

    /**
     * Combine two trees into a new tree.
     *
     * @param x
     * the first tree
     * @param y
     * the second tree
     * @return the combined tree
     */
    private fun combine(x: TreeNode, y: TreeNode): TreeNode {
        val z: TreeNode = TreeNode()
        z.left = x
        x.parent = z
        z.right = y
        y.parent = z
        z.rank = x.rank + 1
        sift(z)
        return z
    }

    /**
     * Update all suffix minimum pointers for a node and all its predecessors in
     * the root list.
     *
     * @param t
     * the node
     */
    private fun updateSuffixMin(t: RootListNode?) {
        var t: RootListNode? = t
        if (comparator == null) {
            while (t != null) {
                if (t.next == null) {
                    t.suffixMin = t
                } else {
                    val nextSuffixMin: RootListNode = t.next!!.suffixMin
                    if ((t.root.cKey as Comparable<K?>?)!!.compareTo(nextSuffixMin.root.cKey) <= 0) {
                        t.suffixMin = t
                    } else {
                        t.suffixMin = nextSuffixMin
                    }
                }
                t = t.prev
            }
        } else {
            while (t != null) {
                if (t.next == null) {
                    t.suffixMin = t
                } else {
                    val nextSuffixMin: RootListNode = t.next!!.suffixMin
                    if (comparator.compare(t.root.cKey, nextSuffixMin.root.cKey) <= 0) {
                        t.suffixMin = t
                    } else {
                        t.suffixMin = nextSuffixMin
                    }
                }
                t = t.prev
            }
        }
    }

    /**
     * Merge a list into the root list. Assumes that the two lists are sorted in
     * non-decreasing order of rank.
     *
     * @param head
     * the list head
     * @param tail
     * the list tail
     */
    private fun mergeInto(head: RootListNode?, tail: RootListNode?) {
        // if root list empty, just copy
        if (rootList.head == null) {
            rootList.head = head
            rootList.tail = tail
            return
        }

        // initialize
        var resultHead: RootListNode?
        var resultTail: RootListNode?
        var resultTailPrev: RootListNode? = null
        var cur1: RootListNode? = rootList.head
        var cur2: RootListNode? = head

        var cur1next: RootListNode?
        var cur2next: RootListNode?
        
        // add first node
        if (cur1!!.root.rank <= cur2!!.root.rank) {
            resultHead = cur1
            resultTail = cur1
            cur1next = cur1.next
            cur1.next = null
            cur1 = cur1next
            if (cur1next != null) {
                cur1next.prev = null
            }
        } else {
            resultHead = cur2
            resultTail = cur2
            cur2next = cur2.next
            cur2.next = null
            cur2 = cur2next
            if (cur2next != null) {
                cur2next.prev = null
            }
        }

        // merge
        var rank1: Int
        var rank2: Int
        while (true) {
            val resultRank: Int = resultTail!!.root.rank

            // read rank1
            if (cur1 != null) {
                rank1 = cur1.root.rank
            } else {
                if (cur2 != null && cur2.root.rank <= resultRank) {
                    rank1 = Int.MAX_VALUE
                } else {
                    break
                }
            }

            // read rank2
            if (cur2 != null) {
                rank2 = cur2.root.rank
            } else {
                if (cur1 != null && cur1.root.rank <= resultRank) {
                    rank2 = Int.MAX_VALUE
                } else {
                    break
                }
            }

            if (rank1 <= rank2) {
                when (Integer.compare(rank1, resultRank)) {
                    0 -> {
                        // combine into result
                        resultTail.root = combine(cur1!!.root, resultTail.root)
                        resultTail.root.parent = resultTail
                        // remove cur1
                        cur1next = cur1.next
                        cur1.next = null
                        if (cur1next != null) {
                            cur1next.prev = null
                        }
                        cur1 = cur1next
                    }

                    -1 -> {
                        // can happen if three same ranks
                        cur1next = cur1!!.next
                        // add before tail into result
                        cur1.next = resultTail
                        resultTail.prev = cur1
                        cur1.prev = resultTailPrev
                        if (resultTailPrev != null) {
                            resultTailPrev.next = cur1
                        } else {
                            resultHead = cur1
                        }
                        resultTailPrev = cur1
                        // advance cur1
                        if (cur1next != null) {
                            cur1next.prev = null
                        }
                        cur1 = cur1next
                    }

                    1 -> {
                        // append into result
                        resultTail.next = cur1
                        cur1!!.prev = resultTail
                        resultTailPrev = resultTail
                        resultTail = cur1
                        // remove cur1
                        cur1 = cur1.next
                        resultTail.next = null
                        if (cur1 != null) {
                            cur1.prev = null
                        }
                    }

                    else -> {}
                }
            } else {
                // symmetric case rank2 < rank1
                when (Integer.compare(rank2, resultRank)) {
                    0 -> {
                        // combine into result
                        resultTail.root = combine(cur2!!.root, resultTail.root)
                        resultTail.root.parent = resultTail
                        // remove cur2
                        cur2next = cur2.next
                        cur2.next = null
                        if (cur2next != null) {
                            cur2next.prev = null
                        }
                        cur2 = cur2next
                    }

                    -1 -> {
                        // can happen if three same ranks
                        cur2next = cur2!!.next
                        // add before tail into result
                        cur2.next = resultTail
                        resultTail.prev = cur2
                        cur2.prev = resultTailPrev
                        if (resultTailPrev != null) {
                            resultTailPrev.next = cur2
                        } else {
                            resultHead = cur2
                        }
                        resultTailPrev = cur2
                        // advance cur2
                        if (cur2next != null) {
                            cur2next.prev = null
                        }
                        cur2 = cur2next
                    }

                    1 -> {
                        // append into result
                        resultTail.next = cur2
                        cur2!!.prev = resultTail
                        resultTailPrev = resultTail
                        resultTail = cur2
                        // remove cur2
                        cur2 = cur2.next
                        resultTail.next = null
                        if (cur2 != null) {
                            cur2.prev = null
                        }
                    }

                    else -> {}
                }
            }
        }

        // record up to which point a suffix minimum update is needed
        val updateSuffixFix: RootListNode? = resultTail

        // here rank of cur1 is more than result rank
        if (cur1 != null) {
            cur1.prev = resultTail
            resultTail!!.next = cur1
            resultTail = rootList.tail
        }

        // here rank of cur2 is more than result rank
        if (cur2 != null) {
            cur2.prev = resultTail
            resultTail!!.next = cur2
            resultTail = tail
        }

        // update suffix minimum
        updateSuffixMin(updateSuffixFix)

        // store final list
        rootList.head = resultHead
        rootList.tail = resultTail
    }

    /**
     * Delete a node from the root list.
     *
     * @param n
     * the node
     */
    private fun deleteNode(n: RootListNode) {
        val nPrev: RootListNode? = n.prev

        if (nPrev != null) {
            nPrev.next = n.next
        } else {
            rootList.head = n.next
        }

        if (n.next != null) {
            n.next!!.prev = nPrev
        } else {
            rootList.tail = nPrev
        }

        n.prev = null
        n.next = null
    }

    /**
     * Delete an element.
     *
     * @param n
     * the element to delete
     */
    private fun delete(n: SoftHandle) {
        if (n.tree == null) {
            throw IllegalArgumentException("Invalid handle!")
        }

        /*
         * Delete from belonging list. Care must be taken as the tree reference
         * is valid only if the node is the first in the list.
         */
        val tree: TreeNode? = n.tree

        if (tree!!.cHead !== n) {
            /*
             * Not first in list. Each case, remove and leave as ghost element.
             */
            if (n.next != null) {
                n.next!!.prev = n.prev
            }
            n.prev!!.next = n.next
        } else {
            /*
             * First in list
             */
            val nNext: SoftHandle? = n.next
            tree!!.cHead = nNext
            if (nNext != null) {
                /*
                 * More elements exists, remove and leave as ghost element.
                 * Update new first element to point to correct tree.
                 */
                nNext.prev = null
                nNext.tree = tree
            } else {
                /*
                 * No more elements, sift.
                 */
                sift(tree)

                /*
                 * If still no elements, remove tree.
                 */
                if (tree.cHead == null) {
                    if (tree.parent is BinaryTreeSoftAddressableHeap<*,*>.TreeNode) {
                        val p = tree.parent as BinaryTreeSoftAddressableHeap<K,V>.TreeNode
                        if (p.left === tree) {
                            p.left = null
                        } else {
                            p.right = null
                        }
                    } else {
                        deleteNode(tree.parent as BinaryTreeSoftAddressableHeap<K,V>.RootListNode)
                    }
                }
            }
        }

        n.tree = null
        n.prev = null
        n.next = null

        size--
    }

    companion object {
        
        /**
         * Already computed values for target sizes.
         */
        private val TARGET_SIZE: LongArray = longArrayOf(
            1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, 1065,
            1598, 2397, 3596, 5394, 8091, 12137, 18206, 27309, 40964, 61446, 92169, 138254, 207381, 311072, 466608,
            699912, 1049868, 1574802, 2362203, 3543305, 5314958, 7972437, 11958656, 17937984, 26906976, 40360464,
            60540696, 90811044, 136216566, 204324849, 306487274, 459730911, 689596367, 1034394551, 1551591827,
            2327387741L, 3491081612L, 5236622418L, 7854933627L, 11782400441L, 17673600662L, 26510400993L, 39765601490L,
            59648402235L, 89472603353L, 134208905030L
        )
    }
}
